package com.zjsru.plan2024.normal;

import java.util.Arrays;

/**
 * 2187. 完成旅途的最少时间
 * @Author: cookLee
 * @Date: 2024-10-07
 */
public class MinimumTime {
    /**
     * 主
     * \
     * 输入：time = [1,2,3], totalTrips = 5
     * 输出：3
     * 解释：
     * - 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
     *   已完成的总旅途数为 1 + 0 + 0 = 1 。
     * - 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
     *   已完成的总旅途数为 2 + 1 + 0 = 3 。
     * - 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
     *   已完成的总旅途数为 3 + 1 + 1 = 5 。
     * 所以总共完成至少 5 趟旅途的最少时间为 3 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinimumTime minimumTime = new MinimumTime();
        int[] time = new int[]{5,10,10};
        int totalTrips = 9;
        System.out.println(minimumTime.minimumTime(time, totalTrips));
    }

    /**
     * 二分法
     *
     * @param time       时间
     * @param totalTrips 总旅行次数
     * @return long
     */
    private long minimumTime(int[] time, int totalTrips) {
        long left = 1;
        //公交可跑的数量最高上限
        long right = (long) Arrays.stream(time).max().orElse(0) * totalTrips;
        while (left < right) {
            long mid = (right - left) / 2 + left;
            if (this.helper(mid, time, totalTrips)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 计算时间是否能完成旅途
     *
     * @param t          当前时间
     * @param time       时间
     * @param totalTrips 总旅行次数
     * @return boolean
     */
    private boolean helper(long t, int[] time, int totalTrips) {
        //所有公交车完成旅途数量的总和
        long count = 0;
        for (int period : time) {
            count += t / period;
        }
        //判断是否满足公交发车数量
        return count >= totalTrips;
    }
}
